%!TEX program = xelatex
%!TEX TS-program = xelatex
%!TEX encoding = UTF-8 Unicode

\documentclass[12pt,t,aspectratio=169,mathserif]{beamer}
%Other possible values are: 1610, 149, 54, 43 and 32. By default, it is to 128mm by 96mm(4:3).
%run XeLaTeX to compile.

\input{wang-slides-preamble.tex}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Applied Stochastic Processes - Lecture 07}
\subtitle{(7.1 - 7.2) Renewal Processes - Renewal Function, Block Replacement}
%(3.1-3.3) 
%\institute{上海立信会计金融学院}
\author{MAP SK}
\date{May 18, 2021}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\begin{enumerate}
%\item 第一讲：March 9 (3.1-3.3) Markov Chains - Concepts and Examples
%\item 第二讲：March 16 (3.4-3.5) Markov Chains - First Step Analysis, More Examples
%\item 第三讲：March 23 (4.1-4.4) Markov Chains - Long Run Behaviors
%\item 第四讲：April 13 (5.1-5.2) Poisson Processes - Concept and Examples 
%\item 第五讲：April 20 (5.3-5.4) Poisson Processes - Associated Distributions  
%\item 第六讲：May 11 (6.1-6.1) Markov Chains - Continuous Time, Pure Birth Processes
%\item 第七讲：May 18 (7.1-7.2) Renewal Processes - Renewal Function, Block Replacement
%\item 第八讲：May 25 (8.1-8.2) Brownian Motions -  the Reflection Principle 
%\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{Contents }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}
\item  Renewal process
\item  Replacements of lightbulbs
\item  Renewal function
\item  Wald identity
\item  Block replacement
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.1. Renewal process }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}

\item  Renewal theory began with the study of stochastic systems whose evolution through time was interspersed with renewals or regeneration times when, in a statistical sense, the process began anew. 

\item  Today, the subject is viewed as the study of general functions of independent, identically distributed, nonnegative random variables representing the successive intervals between renewals. 
The results are applicable in a wide variety of both theoretical and practical probability models.

\item  A renewal (counting) process $\{N(t),t \ge 0\}$ is a nonnegative integer-valued stochastic process that registers the successive occurrences of an event during the time interval $(0,t]$, where the times between consecutive events are positive, independent, identically distributed random variables. 
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.2.  }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}

\item  Let the successive durations between events be $\{X_k\}_{k=1}^{\infty}$ (often representing the lifetimes of some units successively placed into service) such that $X_i$ is the elapsed time from the $(i-1)$st event until the occurrence of the $i$th event. 

\item  We write $F(x) = \mathbb{P}\{X_k \le x\}, k = 1,2,3,\cdots,$ for the common probability distribution of $X_1, X_2, \cdots$. 

\item  A basic stipulation for renewal processes is $F(0) = 0$, signifying that $X_1, X_2, \cdots$ are positive random variables. 

\item  We refer to
\begin{eqnarray}W_n = X_1 + X_2 + \cdots + X_n,\, (n\ge 1), \quad W_0 = 0 \text{ by convention},
\label{eq7-1}
\end{eqnarray}as the waiting time until the occurrence of the $n$th event.

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.3.  }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}

\item  The relation between the inter-occurrence times $\{X_k\}$ and the renewal counting process $\{N(t),t \ge 0\}$ is depicted in the Figure. 

\begin{figure}
\centering
\includegraphics[height=0.5\textheight, width=0.9\textwidth]{pic/renewal-inter-occurrence-times.png}
% \caption{ }
\end{figure}


\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.4. Replacements of lightbulbs }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}


\item  Note formally that
\begin{eqnarray}
N(t) = \text{ number of indices $n$ for which } 0 < W_n \le t.
\label{eq7-2})
\end{eqnarray}

\item  In common practice, the counting process $\{N(t),t \ge 0\}$ and the partial sum process $\{W_n,n \ge 0\}$ are interchangeably called the `renewal process'. 


\item  The prototypical renewal model involves successive replacements of lightbulbs. 
A bulb is installed for service at time $W_0 = 0$, fails at time $W_1 = X_1$, and is then exchanged for a fresh bulb. 

\item  The second bulb fails at time $W_2 = X_1 + X_2$ and is replaced by a third bulb. 

\item  In general, the $n$th bulb burns out at time $W_n = X_1 + \cdots + X_n$ and is immediately replaced, and the process continues. 

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.5.  }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}

\item  It is natural to assume that the successive lifetimes are statistically independent, with probabilistically identical characteristics in that
\begin{eqnarray*}
\mathbb{P}\{ X_k \le x\} = F(x) \text{ for } k = 1,2,\cdots.
%\label{eq7-2})
\end{eqnarray*}

\item  In this process, $N(t)$ records the number of lightbulb replacements up to time $t$.

\item  The principal objective of renewal theory is to derive properties of certain random variables associated with $\{N(t)\}$ and $\{W_n\}$ from knowledge of the inter-occurrence distribution $F$. 

\item  For example, it is of significance and relevance to compute the expected number of renewals for the time duration $(0,t]$: $\mathbb{E}[N(t)] = M(t)$ is called the renewal function. 

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.6.  }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}

\item  To this end, several pertinent relationships and formulas are worth recording. 

\item  In principle, the probability law of $W_n = X_1 + \cdots + X_n$ can be calculated in accordance with the convolution formula 
\begin{eqnarray*}
\mathbb{P}\{ W_n \le x\} = F_n(x),
%\label{eq7-2})
\end{eqnarray*}
where $F_1(x) = F(x)$ is assumed known or prescribed, and then
\begin{eqnarray*}
F_n(x) = \int_0^{\infty} F_{n-1}(x-y)dF(y) = \int_0^{x}F_{n-1}(x − y)dF(y).
%\label{eq7-2})
\end{eqnarray*}

%Such convolution formulas were reviewed in Chapter 1, Section 1.2.5.\item  The fundamental connecting link between the waiting time process $\{W_n\}$ and the renewal counting process $\{N(t)\}$ is the observation that
\begin{eqnarray}
N(t) \ge k \text{ if and only if } W_k \le t.
\label{eq7-3}
\end{eqnarray}

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.7.  }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}

\item  In words, equation (\ref{eq7-3}) asserts that the number of renewals up to time $t$ is at least $k$ if and only if the $k$th renewal occurred on or before time $t$. 

\item  Since this equivalence is the basis for much that follows, the reader should verify instances of it by referring to the Figure above.
\item  It follows from (\ref{eq7-3}) that 
\begin{eqnarray}
\mathbb{P}\{N(t) \ge k\} = \mathbb{P}\{ W_k \le t\} = F_k(t),\,\, t \ge 0,\,\, k = 1,2,\cdots,
\label{eq7-4}
\end{eqnarray}
and consequently,
\begin{eqnarray}
\mathbb{P}\{ N(t) = k\} &=& \mathbb{P}\{N(t) \ge k\} - \mathbb{P}\{ N(t) \ge k + 1\} \nonumber \\ &=& F_k(t) - F_{k+1}(t),\,\,  t\ge 0,k = 1,2,\cdots.
\label{eq7-4}
\end{eqnarray}


\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.8. Renewal function }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}


\item  For the renewal function $M(t) = \mathbb{E}[N(t)]$, we sum the tail probabilities in the manner $\mathbb{E}[N(t)] =  \sum_{k=1}^{\infty} \mathbb{P}\{N(t) \ge k\}$, and then use (\ref{eq7-4}) to obtain\begin{eqnarray}M(t) = \mathbb{E}[N(t)] = \sum_{k=1}^{\infty} \mathbb{P}\{ N(t) \ge k\} = \sum_{k=1}^{\infty} \mathbb{P}\{ W_k \le t\} = \sum_{k=1}^{\infty} F_k(t). \label{eq7-6}
\end{eqnarray}

\item  There are a number of other random variables of interest in renewal theory. 

\item  Three of these are the {\color{red}excess life} (also called the excess random variable), the {\color{red}current life} (also called the age random variable), and the {\color{red}total life}, defined, respectively, by
\begin{eqnarray*}\gamma_t &=& W_{N(t)+1} - t\quad \text{ (excess or residual lifetime)}, \\
\delta_t &=& t - W_{N(t)}\quad \text{ (current life or age random variable)}, \\\beta t &=& \gamma t + \delta t,\quad \text{ (total life)}.
%\label{eq7-6}
\end{eqnarray*}

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.9.  }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}

\item  A pictorial description of these random variables is given in the Figure.

\begin{figure}
\centering
\includegraphics[height=0.5\textheight, width=0.9\textwidth]{pic/excess-current-total-life.png}
% \caption{ }
\end{figure}
\item  An important identity enables us to evaluate the mean of $W_{N(t)+1}$ in terms of the mean lifetime $\mu = \mathbb{E}[X_1]$ of each unit and the renewal function $M(t)$. 

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.10. Wald identity }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}

\item  Namely, it is true for every renewal process that
\begin{eqnarray}
\mathbb{E} [ W_{N(t)+1}] &=& \mathbb{E} [ X_1 + \cdots + X_{N(t)+1}] = \mathbb{E} [ X_1 ] \{\mathbb{E}[N(t) + 1]\} \nonumber \\
&=& \mu \{M(t) + 1\}.
\label{eq7-7}
\end{eqnarray}
%or
%\begin{eqnarray}%\mathbb{E} [W_{N(t)+1}] = \mu \{M(t) + 1\}.
%\label{eq7-7}
%\end{eqnarray}

\item  At first glance, this identity resembles the formula for the mean of a random sum, which asserts that $\mathbb{E}[X_1 +\cdots+X_N] = \mathbb{E}[X_1]\mathbb{E}[N] $ when $N$ is an integer-valued random variable that is independent of $X_1, X_2, \cdots$. 

\item  The random sum approach does not apply in the current context, however, the crucial difference being that the random number of summands $N(t)+1$ is not independent of the summands themselves. 

%\item  Indeed, in Section 7.3, on the Poisson process viewed as a renewal process, we will show that the last summand $X_{N(t)+1}$ has a mean that approaches twice the unconditional mean $\mu = \mathbb{E}[X_1]$ for $t$ large. 

\item  For this reason, it is not correct, in particular, that $\mathbb{E} [ W_{N(t)} ]$ can be evaluated as the product of $\mathbb{E}[X_1]$ and $\mathbb{E}[N(t)]$. 
In view of these comments, the identity expressed in equation (\ref{eq7-7}) becomes more intriguing and remarkable.

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.11. Block replacement }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}

\item  Consider a lightbulb whose life, measured in discrete units, is a random variable $X$, where $
\mathbb{P}\{X = k\} = p_k$ for $k = 1,2,\cdots$. 

\item  Assuming that one starts with a fresh bulb and that each bulb is replaced by a new one when it burns out, let $M(n) = \mathbb{E}[N(n)]$ be the expected number of replacements up to time $n$.

\item  Because of economies of scale, in a large building such as a factory or office it is often cheaper, on a per bulb basis, to replace all the bulbs, failed or not, than it is to replace a single bulb. 

\item  A block replacement policy attempts to take advantage of this reduced cost by fixing a block period $K$ and then replacing bulbs as they fail during periods $1,2,\cdot, K-1$, and replacing all bulbs, failed or not, in period $K$. 

\item  This strategy is also known as `group relamping'. 


\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.12.  }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}


\item  If $c_1$ is the per bulb block replacement cost and $c_2$ is the per bulb failure replacement cost ($c_1 < c_2$), then the mean total cost during the block replacement cycle is $c_1 + c_2M(K-1)$, where $M(K-1) = \mathbb{E}[N(K-1)]$ is the mean number of failure replacements. 

\item  Since the block replacement cycle consists of $K$ periods, the mean total cost per bulb per unit time is
\begin{eqnarray*}
\theta(K) = \frac{c_1 +c_2M(K-1)}{K}.
%\label{eq7-7}
\end{eqnarray*}

\item  If we can determine the renewal function $M(n)$ from the life distribution $\{p_k\}$, then we can choose the block period $K = K^*$ so as to minimize the cost rate $\theta(K)$. 

\item  Of course, this cost must be compared to the cost of replacing only upon failure.

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.13.  }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}


\item  The renewal function $M(n)$, or expected number of replacements up to time $n$, solves the equation
\begin{eqnarray*}
M(n)=F_X(n) + \sum\limits_{k=1}^{n-1} p_k M(n-k) \text{ for } n = 1, 2,\cdots.%\label{eq7-7}
\end{eqnarray*}

\item  To derive this equation, condition on the life $X_1$ of the first bulb. 

\item  If it fails after time $n$, there are no replacements during periods $[1,2,\cdots,n]$. 

\item  On the other hand, if it fails at time $k < n$, then we have its failure plus, on the average, $M(n-k)$ additional replacements during the interval $[k+1, k+2,\cdots,n]$. 

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[fragile=singleslide]{6.1.1. }
\begin{frame}{7.14.  }

\vspace{-0.4cm}\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%每页详细内容

\begin{itemize}


\item  Using the {\color{red}law of total probability} to sum these contributions, we obtain\begin{eqnarray*}M(n) = \sum\limits_{k=n+1}^{\infty}  p_k(0) + \sum\limits_{k=1}^{n} p_k[1+M(n-k)]=F_X(n) + \sum\limits_{k=1}^{n-1} p_kM(n-k), 
%\label{eq7-7}
\end{eqnarray*}
as asserted. 

\item  Thus we determine
\begin{eqnarray*}
M(1) &=& F_X (1), \\
M(2) &=& F_X(2) + p_1M(1), \\
M(3) &=& F_X(3) + p_1M(2) + p_2M(1),
%\label{eq7-7}
\end{eqnarray*}
and so on. 

\end{itemize}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%









